#include <vector>
#include <set>

using namespace std;


class DisjointSets {
private:
    int n;
    vector<int> parents;

public:
    DisjointSets() {};

    DisjointSets(set<int>& vertices) {
        n = vertices.size();
        parents.resize(n+1, -1);  // index 0 is a dummy
        for(const int& u : vertices) {
            parents[u] = u;
        }
    }

    int Find(int u) {
        if (parents[u] == u) return u;
        return parents[u] = Find(parents[u]);
    }

    bool Union(int u, int v) {
        u = Find(u);
        v = Find(v);
        if (u == v) return true;  // redundant edge!

        parents[u] = v;
        return false;
    }
};


/**
 * @brief 684. 冗余连接
 * https://leetcode.cn/problems/redundant-connection/
 */
class Solution {
private:
    DisjointSets dsets;

public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        set<int> vertices;
        for (const vector<int>& edge : edges) {
            vertices.insert(edge[0]);
            vertices.insert(edge[1]);
        }
        dsets = DisjointSets(vertices);

        vector<int> res;
        for (const vector<int>& edge : edges) {
            if (dsets.Union(edge[0], edge[1])) {
                res = edge;
            }
        }

        return res;
    }
};
